#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

void FillRand(int A[], int n);
void RunNumber(int A[], int n);
void CheckSum(int A[], int n);
void FillInc(int A[], int n);
void FillDec(int A[], int n);
int ShakerSort(int A[], int n, int check);
int BubbleSort(int A[], int n);

int main() {
    int n = 100;
    int *A;
    int check = 0;
    A = (int *)malloc(sizeof(int)*n);
    // рандомный
    srand(time(NULL));
    cout << "Рандомный массив: " << endl;
    FillRand(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    cout << "М теория: " << 3*(n*n-n)/4 << endl;
    cout << "C теория: " << (n*n-n)/2 << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    ShakerSort(A, n, 0);
    
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);

    // возрастающий
    cout << endl
         << "Возрастающий массив: " << endl;
    FillInc(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    cout << "М теория: " << 3*(n*n-n)/4 << endl;
    cout << "C теория: " << n-1 << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    ShakerSort(A, n, 0);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    RunNumber(A, n);
    CheckSum(A, n);

    // убывающий
    cout << endl
         << "Убывающий массив: " << endl;
    FillDec(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    cout << "М теория: " << 3*(n*n-n)/4 << endl;
    cout << "C теория: " << (n*n-n)/2 << endl;
    RunNumber(A, n);
    CheckSum(A, n);
    ShakerSort(A, n, 0);
    CheckSum(A, n);
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
    
    RunNumber(A, n);
    CheckSum(A, n);
    //BubbleSort(A, 100);
    cout << endl << setw(2) << "n" << setw(12) << "М+С  " << setw(20) << "    Мф+Сф пузыр " << setw(14) << "    М+С  " << setw(18) << "       Мф+Сф шейкер" << endl;
    cout << setw(2) << "" << setw(12) << "    теорет  " << setw(17) << " убыв случ  возр " << setw(12) << "   теорет " << setw(17) << "     убыв  случ  возр" << endl;
    cout << setw(50) << "-------------------------------------------------------------------" << endl;
    
    //100, пузырёк
    FillDec(A, n);
    int kp_yb = BubbleSort(A, n);
    FillInc(A, n);
    int kp_voz = BubbleSort(A, n);
    FillRand(A, n);
    int kp_rand = BubbleSort(A, n);
    //шейкер
    FillDec(A, n);
    int ks_yb = ShakerSort(A, n, 1);
    FillInc(A, n);
    int ks_voz = ShakerSort(A, n, 1);
    FillRand(A, n);
    int ks_rand = ShakerSort(A, n, 1);
    cout << setw(2) << "100" << setw(8) << ((n*n-n)/2)+(3*((n*n-n)/2)/2) << setw(8) << kp_yb << setw(5) << kp_rand << setw(6) << kp_voz << setw(10) << (3*(n*n-n)/4)+((n*n-n)/2) << setw(11) << ks_yb << setw(6) << ks_rand << setw(5) << ks_voz << endl;
    cout << setw(50) << "-------------------------------------------------------------------" << endl;
    
    //200, пузырёк
    n = 200;
    FillDec(A, n);
    kp_yb = BubbleSort(A, n);
    FillInc(A, n);
    kp_voz = BubbleSort(A, n);
    FillRand(A, n);
    kp_rand = BubbleSort(A, n);
    //шейкер
    FillDec(A, n);
    ks_yb = ShakerSort(A, n, 1);
    FillInc(A, n);
    ks_voz = ShakerSort(A, n, 1);
    FillRand(A, n);
    ks_rand = ShakerSort(A, n, 1);
    cout << setw(2) << "200" << setw(8) << ((n*n-n)/2)+(3*((n*n-n)/2)/2) << setw(8) << kp_yb << " " << setw(5) << kp_rand << " " << setw(5) << kp_voz << " " << setw(8) << (3*(n*n-n)/4)+((n*n-n)/2) << " " << setw(10) << ks_yb << " " << setw(6) << ks_rand << " " << setw(4) << ks_voz << endl;
    cout << setw(50) << "-------------------------------------------------------------------" << endl;
    
    //300, пузырёк
    n = 300;
    FillDec(A, n);
    kp_yb = BubbleSort(A, n);
    FillInc(A, n);
    kp_voz = BubbleSort(A, n);
    FillRand(A, n);
    kp_rand = BubbleSort(A, n);
    //шейкер
    FillDec(A, n);
    ks_yb = ShakerSort(A, n, 1);
    FillInc(A, n);
    ks_voz = ShakerSort(A, n, 1);
    FillRand(A, n);
    ks_rand = ShakerSort(A, n, 1);
    cout << setw(2) << "300" << setw(8) << ((n*n-n)/2)+(3*((n*n-n)/2)/2) << setw(8) << kp_yb << " " << setw(5) << kp_rand << " " << setw(5) << kp_voz << " " << setw(9) << (3*(n*n-n)/4)+((n*n-n)/2) << " " << setw(9) << ks_yb << " " << setw(6) << ks_rand << " " << setw(4) << ks_voz << endl;
    cout << setw(50) << "-------------------------------------------------------------------" << endl;
    
    //400, пузырёк
    n = 400;
    FillDec(A, n);
    kp_yb = BubbleSort(A, n);
    FillInc(A, n);
    kp_voz = BubbleSort(A, n);
    FillRand(A, n);
    kp_rand = BubbleSort(A, n);
    //шейкер
    FillDec(A, n);
    ks_yb = ShakerSort(A, n, 1);
    FillInc(A, n);
    ks_voz = ShakerSort(A, n, 1);
    FillRand(A, n);
    ks_rand = ShakerSort(A, n, 1);
    cout << setw(2) << "400" << setw(8) << ((n*n-n)/2)+(3*((n*n-n)/2)/2) << setw(8) << kp_yb << " " << setw(5) << kp_rand << " " << setw(5) << kp_voz << " " << setw(8) << (3*(n*n-n)/4)+((n*n-n)/2) << " " << setw(9) << ks_yb << " " << setw(6) << ks_rand << " " << setw(4) << ks_voz << endl;
    cout << setw(50) << "-------------------------------------------------------------------" << endl;
    
    //500, пузырёк
    n = 500;
    FillDec(A, n);
    kp_yb = BubbleSort(A, n);
    FillInc(A, n);
    kp_voz = BubbleSort(A, n);
    FillRand(A, n);
    kp_rand = BubbleSort(A, n);
    //шейкер
    FillDec(A, n);
    ks_yb = ShakerSort(A, n, 1);
    FillInc(A, n);
    ks_voz = ShakerSort(A, n, 1);
    FillRand(A, n);
    ks_rand = ShakerSort(A, n, 1);
    cout << setw(2) << "500" << setw(8) << ((n*n-n)/2)+(3*((n*n-n)/2)/2) << setw(8) << kp_yb << " " << setw(5) << kp_rand << " " << setw(5) << kp_voz << " " << setw(7) << (3*(n*n-n)/4)+((n*n-n)/2) << " " << setw(9) << ks_yb << " " << setw(6) << ks_rand << " " << setw(4) << ks_voz << endl;
    cout << setw(50) << "-------------------------------------------------------------------" << endl;
}

int ShakerSort(int A[], int n, int check){
    int L = 0, R = n-1, K = n-1;
    int M = 0, C = 0;
    while(L < R) {
        for(int j = R; j > L; j--){
            C++;
            if(A[j] < A[j-1]){
                M++;
                swap(A[j], A[j-1]);
                K = j;
            }
        }
        L = K;
        for(int j = L; j < R; j++){
            C++;
            if(A[j] > A[j+1]){
                M++;
                swap(A[j], A[j+1]);
                K = j;
            }
        }
        R = K;
    }
    if(check == 0){
        cout << "М по факту: " << M << endl;
        cout << "C по факту: " << C << endl;
    }
    return M+C;
}

void FillRand(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = rand() % 1000;
    }
}

void RunNumber(int A[], int n) {
    int r = 1;
    for (int i = 1; i < n; i++) {
        if (A[i - 1] > A[i])
            r++;
    }
    cout << "Серий: " << r << endl;
}

void CheckSum(int A[], int n) {
    long int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += A[i];
    }
    cout << "Сумма: " << sum << endl;
}

void FillInc(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = i + 1;
    }
}

void FillDec(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = n - i;
    }
}

int BubbleSort(int A[], int n) {
    int M = 0, C = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            C++;
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
                M++;
            }
        }
    }
    return M+C;
}
